package com.sx.sx1.lintcode.day717;

public class LC247 {


      static class SegmentTreeNode {
          public int start, end, count;
          public SegmentTreeNode left, right;
          public SegmentTreeNode(int start, int end, int count) {
              this.start = start;
              this.end = end;
              this.count = count;
              this.left = this.right = null;
          }
      }



    static class Solution {
        /*
         * @param root: The root of segment tree.
         * @param start: start value.
         * @param end: end value.
         * @return: The count number in the interval [start, end]
         */
        public int query(SegmentTreeNode root, int start, int end) {
            if(root ==null) return 0;
            if(start<= root.start && end >= root.end) return root.count;
            int m = root.start+(root.end-root.start)/2;

            int left=0;
            int right =0;

            if(m>=start){
                left = query(root.left,start,Math.min(m,end));
            }

            if(m<end){
                right = query(root.right,m>=start?m+1:start,end);
            }

            return left+right;
        }
    }

}


/*

// LC 47 · 线段树查询 II vip 中等  递归
public class LC247 {

    static class SegmentTreeNode {
        public int start, end, count;
        public SegmentTreeNode left, right;

        public SegmentTreeNode(int start, int end, int count) {
            this.start = start;
            this.end = end;
            this.count = count;
            this.left = this.right = null;
        }
    }

    public static int query(SegmentTreeNode root, int start, int end) {
        if(root ==null) return 0;
        if (root.start >= start && root.end <= end) {
            return root.count;
        }

        int mid = (root.start + root.end) / 2;
        int left = 0;
        int right = 0;


        if (mid >= start) {
            if (mid < end) {
                right = query(root.left, start,mid);
            } else {
                right = query(root.left, start, end);
            }
        }

        if (mid < end) {
            if (mid >= start) {
                left = query(root.right, mid+1, end);
            } else {
                left = query(root.right, start, end);
            }
        }
        return left + right;
    }
}









LintCode-Logo
学习
刷题
题集
群组

内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有391条未读消息，请及时查看
247 · 线段树查询 II
算法
中等
通过率
32%
题目
题解10
笔记
讨论99+
排名
记录
描述
对于一个数组，我们可以对其建立一棵 线段树, 每个结点存储一个额外的值 count 来代表这个结点所指代的数组区间内的元素个数. (数组中的某些位置可能没有元素)

实现一个 query 的方法，该方法接受三个参数 root, start 和 end, 分别代表线段树的根节点和需要查询的区间，找到数组中在区间[start, end]内的元素个数。

【附答案】花高价求来的OpenAI题库，仅限前50份！

微信加sunny【jiuzhang1104】备注【AI】即可领取


为了能更好地理解这道题，你最好先完成线段树的构造和线段树的查询

样例
样例 1:

输入："[0,3,count=3][0,1,count=1][2,3,count=2][0,0,count=1][1,1,count=0][2,2,count=1][3,3,count=1]",[[1, 1], [1, 2], [2, 3], [0, 2]]
输出：[0,1,2,2]
解释：
对应的线段树为：

	                     [0, 3, count=3]
	                     /             \
	          [0,1,count=1]             [2,3,count=2]
	          /         \               /            \
	   [0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]

Input : query(1,1), Output: 0

Input : query(1,2), Output: 1

Input : query(2,3), Output: 2

Input : query(0,2), Output: 2
样例 2:

输入："[0,3,count=3][0,1,count=1][2,3,count=2][0,0,count=1][1,1,count=0][2,2,count=0][3,3,count=1]",[[1, 1], [1, 2], [2, 3], [0, 2]]
输出：[0,0,1,1]
解释：
对应的线段树为：

	                     [0, 3, count=2]
	                     /             \
	          [0,1,count=1]             [2,3,count=1]
	          /         \               /            \
	   [0,0,count=1] [1,1,count=0] [2,2,count=0], [3,3,count=1]

Input : query(1,1), Output: 0

Input : query(1,2), Output: 0

Input : query(2,3), Output: 1

Input : query(0,2), Output: 1
标签
相关题目

201
线段树的构造
中等

202
线段树的查询
中等

203
线段树的修改
中等
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
14/20
已开启智能提示
发起考试
30 分 00 秒
1234567891011121314151617181920212223242526
 *     }
 * }
 */
